package everyday;

import java.util.Stack;

/**
 * @author zhangmin
 * @create 2022-04-27 16:21
 * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
 *
 * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
 *
 * 思路：
 * 找到每个位置左边和右边分别连续比当前位置高的下标
 * 可以使用单调栈，在两边找下一个比当前位置低的下标
 */
public class largestRectangleArea84 {
    public int largestRectangleArea(int[] heights) {
        int n=heights.length;
        int[] left=new int[n],right=new int[n];
        Stack<Integer> stack=new Stack<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty()&&heights[stack.peek()]>=heights[i]){
                stack.pop();
            }
            left[i]=stack.isEmpty()?-1:stack.peek();
            stack.push(i);
        }
        stack.clear();
        for (int i = n-1; i >=0; i--) {
            while (!stack.isEmpty()&&heights[stack.peek()]>=heights[i]){
                stack.pop();
            }
            right[i]=stack.isEmpty()?n:stack.peek();
            stack.push(i);
        }
        int res=0;
        for (int i = 0; i < n; i++) {
            int area=(right[i]-left[i]-1)*heights[i];
            res=Math.max(res,area);
        }
        return res;
    }
}
